2020 CUSTACM Freshman Contest - Onsite - Editorial

发表于 更新于 分类于 阅读次数： 评论数：
本文字数： 1.4k 阅读时长 ≈ 5 分钟
本文记录了2020CUST纳新赛的一血代码

A:PaperCube and Dimensionality Reduction

Description

多组输入到文件尾求 $n^2$ 的末位数字。

Code

First Blood by team76116

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>

using namespace std;

int main(){
	typedef long long ll;
	ll x;
	while(cin >> x){
		cout << (x * x % 10) << endl;
	}	
}

B：PaperSquare’s law

Description

多组输入到文件尾求 $n^2$ 的首位数字。

Code

First Blood by team76006

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
int main(){
	long long a,b;
	while(~scanf("%lld",&a)){
		
	b=a*a;
	while(b>=10)b/=10;
	printf("%lld\n",b);
	
	}
	return 0;
}

C：Powerful PaperCube

Description

多组输入到文件尾求 $2^n$ 的末位数字。

Code

First Blood by team76116

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>

using namespace std;

int main(){
	typedef long long ll;
	ll x;
	while(cin >> x){
		if(x == 0) cout << 1 << endl;
		else cout << "2486"[(x - 1) % 4] << endl;
	}	
}

D：PowerCube’s law

Description

多组输入到文件尾求 $2^n$ 的首位数字。

Solution

$ans = (2^n)/(10^{x-1}) , x= log_{10}(x)+1$

Code

First Blood by team76015

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
double biao[]={0,log(1),log(2),log(3),log(4),log(5),log(6),log(7),log(8),log(9)};

int main(){
    int n;
    double lg=log(10),l2=log(2);
    while(cin>>n){
        double n2=l2*n;
        double ans=lg*floor(n2/lg);
//        while(ans+lg<n2)ans+=lg;
        cout<<(upper_bound(biao,biao+10,n2-ans)-biao-1)<<'\n';
    }
    return 0;
}

E：PaperCube Tree

Description

给定长度为 $n$ 序列 $a$, $q$ 次询问区间 $ai,a{i+1} \cdots a_{j-1},a_j$ 中第 $k$ 大的数。

Code

First Blood by team76001

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <deque>
#include <set>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <ctime>
#include <queue>
#include <stack>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <fstream>
#include <bitset>
#include <complex>
#include <numeric>
//#include "utils/haha.h"
//#include "utils/max_flow.h"
using namespace std;
typedef pair<int, int> PII;
typedef pair<string, string> PSS;
typedef pair<string, int> PSI;
typedef pair<int, PII> PIP;
typedef long long ll;
typedef pair<int, ll> PIL;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<ll, PII> PLP;

template<typename T>
inline T read_by_char() {
  T s = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    s = (s << 3) + (s << 1) + ch - 48;
    ch = getchar();
  }
  return s * f;
}
#define ri() read_by_char<int>()
#define rl() read_by_char<ll>()

#define CLS(x, v) (memset((x), (v), sizeof((x))))

template<class TH>
void _dbg(const char *sdbg, TH h) { cerr << sdbg << '=' << h << endl; }
template<class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
  while (*sdbg != ',')cerr << *sdbg++;
  cerr << '=' << h << ',';
  _dbg(sdbg + 1, a...);
}

template<class T>
ostream &operator<<(ostream &os, vector<T> V) {
  os << "[";
  for (auto vv : V) os << vv << ",";
  return os << "]";
}
template<class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}

#ifdef _zzz_
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

template<class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<class T>
using max_heap = priority_queue<T>;
//const int N = 1e6 + 1e5 + 10;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

struct PairHash {
  template<typename T1, typename T2>
  std::size_t operator()(const pair<T1, T2> &p) const {
    return hash<T1>()(p.first) ^ hash<T2>()(p.second);
  }
};

template<unsigned MOD_>
struct ModInt {
  static constexpr unsigned MOD = MOD_;
  unsigned x;
  void undef() { x = (unsigned) -1; }
  bool isnan() const { return x == (unsigned) -1; }
  inline int geti() const { return (int) x; }
  ModInt() { x = 0; }
  ModInt(const ModInt &y) { x = y.x; }
  ModInt(int y) {
    if (y < 0 || (int) MOD <= y) y %= (int) MOD;
    if (y < 0) y += MOD;
    x = y;
  }
  ModInt(unsigned y) { if (MOD <= y) x = y % MOD; else x = y; }
  ModInt(long long y) {
    if (y < 0 || MOD <= y) y %= MOD;
    if (y < 0) y += MOD;
    x = y;
  }
  ModInt(unsigned long long y) { if (MOD <= y) x = y % MOD; else x = y; }
  ModInt &operator+=(const ModInt y) {
    if ((x += y.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(const ModInt y) {
    if ((x -= y.x) & (1u << 31)) x += MOD;
    return *this;
  }
  ModInt &operator*=(const ModInt y) {
    x = (unsigned long long) x * y.x % MOD;
    return *this;
  }
  ModInt &operator/=(const ModInt y) {
    x = (unsigned long long) x * y.inv().x % MOD;
    return *this;
  }
  ModInt operator-() const { return (x ? MOD - x : 0); }

  ModInt inv() const { return pow(MOD - 2); }
  ModInt pow(long long y) const {
    ModInt b = *this, r = 1;
    if (y < 0) {
      b = b.inv();
      y = -y;
    }
    for (; y; y >>= 1) {
      if (y & 1) r *= b;
      b *= b;
    }
    return r;
  }

  friend ModInt operator+(ModInt x, const ModInt y) { return x += y; }
  friend ModInt operator-(ModInt x, const ModInt y) { return x -= y; }
  friend ModInt operator*(ModInt x, const ModInt y) { return x *= y; }
  friend ModInt operator/(ModInt x, const ModInt y) { return x *= y.inv(); }
  friend bool operator<(const ModInt x, const ModInt y) { return x.x < y.x; }
  friend bool operator==(const ModInt x, const ModInt y) { return x.x == y.x; }
  friend bool operator!=(const ModInt x, const ModInt y) { return x.x != y.x; }
};
const int mod = (1e9) + 7;
typedef ModInt<mod> mod_int;

const int MAX_N = 100000;
int N, M;
int A[MAX_N];
int S[MAX_N];

const int MAX_NN = (1 << 17);
int NN;
vector<int> seg[2 * MAX_NN - 1];

void build(int u, int l, int r) {
  if (l + 1 == r) {
    if (l < N)
      seg[u].push_back(A[l]);
    return;
  }

  int m = (l + r) / 2;
  build(u * 2 + 1, l, m);
  build(u * 2 + 2, m, r);
  seg[u].resize(r - l);
  merge(seg[u * 2 + 1].begin(), seg[u * 2 + 1].end(),
        seg[u * 2 + 2].begin(), seg[u * 2 + 2].end(),
        seg[u].begin());
}

// return the number of items in [a, b) is less than val
int query(int a, int b, int val, int u, int l, int r) {
  if (l >= b || r <= a) {
    return 0;
  }

  if (a <= l && r <= b) {
    return upper_bound(seg[u].begin(), seg[u].end(), val) -
        seg[u].begin();
  }

  int m = (l + r) / 2;
  int cnt1 = query(a, b, val, u * 2 + 1, l, m);
  int cnt2 = query(a, b, val, u * 2 + 2, m, r);
  return cnt1 + cnt2;
}

// find the k-th smallest number in [a, b)
int solve(int a, int b, int k) {
  // binary search on index of S
  // C(x) = is the number which is less than S[x] >= k - 1
  // 0 0 0 1 1 1, first 1

  int lb = 0, ub = N - 1;

  if (query(a, b, S[lb], 0, 0, NN) >= k)
    return S[lb];
  // if (query(a, b, S[ub], 0, 0, NN) < k - 1)
  // impossible;
  while (ub - lb > 1) {
    int mid = (lb + ub) / 2;
    if (query(a, b, S[mid], 0, 0, NN) >= k) ub = mid;
    else lb = mid;
  }

  return S[ub];
}

void solve(int ncase) {
  scanf("%d %d", &N, &M);
  for (int i = 0; i < N; i++)
    scanf("%d", &A[i]);

  copy(A, A + N, S);
  sort(S, S + N);

  NN = 1;
  while (NN < N)
    NN <<= 1;
  build(0, 0, NN);

  while (M--) {
    int a, b, k;
    scanf("%d %d %d", &a, &b, &k);
    a--;
    b--;
    printf("%d\n", solve(a, b + 1, k));
  }

}

void solve_all_cases() {
  int T = 1;
  //scanf("%d", &T);
  //cin >> T;
  int ncase = 0;
  //pre_calc();
  while (T--) {
    solve(++ncase);
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << std::fixed;
  cout << setprecision(2);
#ifdef _zzz_
  //ios_base::sync_with_stdio(true);
  freopen("C:\\Users\\grain\\Desktop\\in.txt", "r", stdin);
  //auto x = freopen("C:\\Users\\grain\\Desktop\\out.txt", "w", stdout);
  //cerr << x << " " << errno << endl;
  auto start_time = clock();
#endif
  solve_all_cases();
  //test();
#ifdef _zzz_
  cout << (clock() - start_time) * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
#endif
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

F:Panicubeeeeeeeeeeeeee

Description

多组输入到文件尾,判断 $n.0/m$ 是不是循环数位为 $1$ 的的循环小数(形如Panicubeeeeeeeeeeeeee(无数个e))。

Code

First Blood byteam76093

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,m;
	int a;
	while(scanf("%lld%lld",&n,&m)!=EOF)
	{
		a=0;
		m/=__gcd(n,m);
		while(m)
		{
			if(m%3==0)
			{
				m/=3;
				a++;
			}
			else if(m%2==0)m/=2;
			else if(m%5==0)m/=5;
			else break;
		}
		if(m!=1||!a||a>2)puts("NO");
		else puts("YES");
	}
}

G:Piling up PaperCubes

Description

在 $n$ 行 $m$ 列的区域里放置纸盒，给出 $q$ 组操作，每次告诉你新纸盒的位置在 $i$ 行 $j$ 列，输出最后纸盒的情况。以左上角为$(0,0)$，下数为第几行，右数为第几列。

Code

First Blood byteam76001

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <deque>
#include <set>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <ctime>
#include <queue>
#include <stack>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <fstream>
#include <bitset>
#include <complex>
#include <numeric>
//#include "utils/haha.h"
//#include "utils/max_flow.h"
using namespace std;
typedef pair<int, int> PII;
typedef pair<string, string> PSS;
typedef pair<string, int> PSI;
typedef pair<int, PII> PIP;
typedef long long ll;
typedef pair<int, ll> PIL;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<ll, PII> PLP;

template<typename T>
inline T read_by_char() {
  T s = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    s = (s << 3) + (s << 1) + ch - 48;
    ch = getchar();
  }
  return s * f;
}
#define ri() read_by_char<int>()
#define rl() read_by_char<ll>()

#define CLS(x, v) (memset((x), (v), sizeof((x))))

template<class TH>
void _dbg(const char *sdbg, TH h) { cerr << sdbg << '=' << h << endl; }
template<class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
  while (*sdbg != ',')cerr << *sdbg++;
  cerr << '=' << h << ',';
  _dbg(sdbg + 1, a...);
}

template<class T>
ostream &operator<<(ostream &os, vector<T> V) {
  os << "[";
  for (auto vv : V) os << vv << ",";
  return os << "]";
}
template<class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}

#ifdef _zzz_
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

template<class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<class T>
using max_heap = priority_queue<T>;
//const int N = 1e6 + 1e5 + 10;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

struct PairHash {
  template<typename T1, typename T2>
  std::size_t operator()(const pair<T1, T2> &p) const {
    return hash<T1>()(p.first) ^ hash<T2>()(p.second);
  }
};

template<unsigned MOD_>
struct ModInt {
  static constexpr unsigned MOD = MOD_;
  unsigned x;
  void undef() { x = (unsigned) -1; }
  bool isnan() const { return x == (unsigned) -1; }
  inline int geti() const { return (int) x; }
  ModInt() { x = 0; }
  ModInt(const ModInt &y) { x = y.x; }
  ModInt(int y) {
    if (y < 0 || (int) MOD <= y) y %= (int) MOD;
    if (y < 0) y += MOD;
    x = y;
  }
  ModInt(unsigned y) { if (MOD <= y) x = y % MOD; else x = y; }
  ModInt(long long y) {
    if (y < 0 || MOD <= y) y %= MOD;
    if (y < 0) y += MOD;
    x = y;
  }
  ModInt(unsigned long long y) { if (MOD <= y) x = y % MOD; else x = y; }
  ModInt &operator+=(const ModInt y) {
    if ((x += y.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(const ModInt y) {
    if ((x -= y.x) & (1u << 31)) x += MOD;
    return *this;
  }
  ModInt &operator*=(const ModInt y) {
    x = (unsigned long long) x * y.x % MOD;
    return *this;
  }
  ModInt &operator/=(const ModInt y) {
    x = (unsigned long long) x * y.inv().x % MOD;
    return *this;
  }
  ModInt operator-() const { return (x ? MOD - x : 0); }

  ModInt inv() const { return pow(MOD - 2); }
  ModInt pow(long long y) const {
    ModInt b = *this, r = 1;
    if (y < 0) {
      b = b.inv();
      y = -y;
    }
    for (; y; y >>= 1) {
      if (y & 1) r *= b;
      b *= b;
    }
    return r;
  }

  friend ModInt operator+(ModInt x, const ModInt y) { return x += y; }
  friend ModInt operator-(ModInt x, const ModInt y) { return x -= y; }
  friend ModInt operator*(ModInt x, const ModInt y) { return x *= y; }
  friend ModInt operator/(ModInt x, const ModInt y) { return x *= y.inv(); }
  friend bool operator<(const ModInt x, const ModInt y) { return x.x < y.x; }
  friend bool operator==(const ModInt x, const ModInt y) { return x.x == y.x; }
  friend bool operator!=(const ModInt x, const ModInt y) { return x.x != y.x; }
};
const int mod = (1e9) + 7;
typedef ModInt<mod> mod_int;

vector<string> box =
    {
        "..+-------+",
        "./  7 7  /|",
        "+-------+ |",
        "| paper | +",
        "| cube  |/.",
        "+-------+.."
    };

void write_box(vector<string> &ret, string &empty_row, int x, int y) {
  while (ret.size() <= x + 5) ret.push_back(empty_row);
  for (int i = 5; i >= 0; i--) {
    for (int j = 0; j < box[i].size(); j++) {
      if (box[i][j] == '.') continue;
      ret[x + (5 - i)][y + j] = box[i][j];

      //debug(x + 5 - i, y + j, i, j);
    }
  }
}

void solve(int ncase) {
  int n, m, d;
  cin >> n >> m >> d;
  vector<vector<int>> cnt(n, vector<int>(m));
  for (int i = 0; i < d; i++) {
    int x, y;
    cin >> x >> y;
    cnt[x - 1][y - 1]++;
  }
  int col = 8 * m + 3 + 2 * n - 2;
  int row = 2 * n + 1;
  string empty_row = string(col, '.');
  vector<string> ret(row, empty_row);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {

      int x = (n - 1 - i) * 2;
      int y = j * 8 + (n - 1 - i) * 2;
      for (int k = 0; k < cnt[i][j]; k++) {

        debug(x, y, i, j);
        write_box(ret, empty_row, x, y);

        x += 3;
      }
    }
  }
  for (int i = ret.size() - 1; i >= 0; i--) {
    cout << ret[i] << endl;
  }
}

void solve_all_cases() {
  int T = 1;
  //scanf("%d", &T);
  //cin >> T;
  int ncase = 0;
  //pre_calc();
  while (T--) {
    solve(++ncase);
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << std::fixed;
  cout << setprecision(2);
#ifdef _zzz_
  //ios_base::sync_with_stdio(true);
  freopen("C:\\Users\\grain\\Desktop\\in.txt", "r", stdin);
  //auto x = freopen("C:\\Users\\grain\\Desktop\\out.txt", "w", stdout);
  //cerr << x << " " << errno << endl;
  auto start_time = clock();
#endif
  solve_all_cases();
  //test();
#ifdef _zzz_
  cout << (clock() - start_time) * 1.0 / CLOCKS_PER_SEC << " seconds" << endl;
#endif
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

H.PaperCube Stacks

Description

给出两个栈：第一个栈依次压入 $1,2,3,4,…,n$；第二个栈依次压入 $n+1,n+2,n+3,…,n+m$；
你可以将栈 $1$ 中的栈顶元素 $pop$ 出，放到栈 $2$ 的顶部；或者将栈 $2$ 中的栈顶元素 $pop$ 出。求将所有元素最后通过栈2 $pop$ 出后，有几种出栈方式。

Code

First Blood by team76001

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
#define mo 114514199
#define ll long long
using namespace std;
char ch[100010];
ll n,m,ans,c[2010][2010];
ll qp(ll a,ll b)
{
	ll re=1,ch=a;
	while(b)
	{
		if(b&1)re=re*ch%mo;
		ch=ch*ch%mo;
		b>>=1;
	}
	return re;
}
int main()
{
	int T;
	//scanf("%d",&T);
	for(int i=0;i<=1000;i++)
	c[0][i]=1;
	for(int i=1;i<=2000;i++)
	{
		c[i][0]=c[i-1][1];
		for(int j=1;j<=2000;j++)
		{
			c[i][j]=c[i-1][j+1]+c[i][j-1];
			c[i][j]%=mo;
		//	printf("%lld ",c[i][j]);
		}
	//	puts("");
	}
	while(scanf("%lld%lld",&n,&m)!=EOF)
	{
//		if(n==0)ans=1;
//		else ans=c[2*n][n+1]*qp(n,mo-2)%mo;
//		ans=ans*(m+1)%mo;
		printf("%lld\n",c[n][m]);
	}
}
/*
2 2
0 0
1 1

4   14
1 2 3 4  4
1 2 4 3  3
1 3 2 4  3
1 3 4 2  
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
3 2 1 4
3 2 4 1
3 4 2 1
4 3 2 1
*/

I:PaperCubes were there

Description

给一个 $n$ 行 $m$ 列的区域，统计区域中有多少个$O$ 组成的立方体平面展开。这些立方体平面展开不考虑相连的情况。

Solution

11 cases
an naive idea: 暴力枚举所有可能的情况，包括镜面，旋转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <random>
#include <cmath>
#include <chrono>
#include <cstring>
#include <string>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#include <cassert>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
using LL = long long;
#define eps 1e-8
#define fi first
#define se second
#define endl '\12'
#define eb emplace_back
#define SZ(a) int32_t(a.size())
#define ALL(x) (x).begin(),(x).end()
#define trav(a,x) for (auto& a: x)
#define LOG(FMT...) fprintf(stderr, FMT)
#define close std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define FOR(i, x, y) for (LL i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (LL i = (x), _##i = (y); i > _##i; --i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define CASET int ___T; cin>>___T; for(int __CS=1;__CS<=___T;__CS++)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
constexpr int mod = 1e9+7;
constexpr int Erica = 998244353;
mt19937 dlsrand(random_device{}());
mt19937 mrand(std::chrono::system_clock::now().time_since_epoch().count()); 
int rnd(int x) { return mrand() % x;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll ex_gcd(ll a, ll b, ll& x, ll& y){if(!b){x=1;y=0;return a;}ll ret=ex_gcd(b,a%b,y,x);y-=a/b*x;return ret;}
LL bin(LL x, LL n, LL MOD) {LL ret = MOD != 1;for (x %= MOD; n; n >>= 1, x = x * x % MOD)if (n & 1) ret = ret * x % MOD;return ret;}
int norm(int x) { return x >= mod ? (x - mod) : x; }
inline LL get_inv(LL x, LL p) { return bin(x, p - 2, p); }
inline ll get_inv(ll a) { ll x, y; ex_gcd(a, mod, x, y); return norm(x + mod);}
template<class T>inline void umin(T &x, T y) {x = x > y ? y : x;}
template<class T>inline void umax(T &x, T y) {x = x < y ? y : x;}
template<class T>inline void dec(T &x, T y) {x -= y; if(x < 0) x += mod;}
template<class T>inline void add(T &x, T y) {x += y; if(x >= mod) x -= mod;}
const double PI = acos(-1.0);
constexpr int INF = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3f;
constexpr ull base=2333, P_1=19260817, P_2=999998639;
constexpr int maxn = 1e6+10; // remember to calculate. if tle, check maxn first.
int n , m, color = 0;
char s[50][50];
int vis[50][50];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int main()
{
    // freopen("6.in","r",stdin);
    // freopen("out.txt","w",stdout);
    close;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> (s[i]+1);
    }
    auto ck = [&](int x, int y){
        if(x < 1 || x > n || y < 1 || y > m || vis[x][y] || s[x][y] != 'O'){
            return 0;
        }
        return 1;
    };
    auto init = [&](){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(s[i][j] == 'O' && vis[i][j] == 0){
                    vis[i][j] = ++color;
                    queue<pii> q;
                    q.push({i, j});
                    while(q.size()){
                        auto x = q.front().first, y = q.front().second;
                        q.pop();
                        for(int k = 0; k < 4; k++){
                            int xx = x + dx[k], yy = y + dy[k];
                            if(ck(xx, yy)){
                                vis[xx][yy] = color;
                                q.push({xx, yy});
                            }
                        }
                    }
                }
            }
        }
        for(int co = 1; co <= color; co++){
            vector<pii> tp;
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    if(vis[i][j] == co){
                        tp.eb(i,j);
                    }
                }
            }
            if(SZ(tp)!=6){
                for(auto [a, b] : tp){
                    s[a][b] = '.';
                }
            }
        }
    };
    init();
    // cout << "\n\n show == \n";
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= m; j++){
    //         cout << s[i][j] ;
    //     }cout << endl;
    // }
    int ans = 0;
    auto chk = [&](int i , int j){
        // cout << "s[" <<i << "][" << j<<"]==="<<s[i][j] << endl;
        if(i < 1 || i > n || j < 1 || j > m || (s[i][j] != 'O')) return 0;
        return 1;
    };
    auto check1 = [&](int i , int j){
        if(chk(i,j) && chk(i,j+1) && chk(i,j+2) && chk(i+1,j+1) && chk(i+2,j+1) && chk(i+3,j+1)){
            ans++;
            // cout << "done  1" << endl;
            s[i][j] = s[i][j+1] = s[i][j+2] = s[i+1][j+1] = s[i+2][j+1] = s[i+3][j+1] = '.';
        }
    };
    auto check2 = [&](int i , int j){
        if(chk(i,j) && chk(i,j+1) && chk(i+1,j+2) && chk(i+1,j+1) && chk(i+2,j+1) && chk(i+3,j+1)){
            ans++;
            // cout << "done  2" << endl;
            s[i][j] = s[i][j+1] = s[i+1][j+2] = s[i+1][j+1] = s[i+2][j+1] = s[i+3][j+1] = '.';
        }
    };
    auto check3 = [&](int i , int j){
        if(chk(i,j) && chk(i,j+1) && chk(i+2,j+2) && chk(i+1,j+1) && chk(i+2,j+1) && chk(i+3,j+1)){
            ans++;
            // cout << "done  3" << endl;
            s[i][j] = s[i][j+1] = s[i+2][j+2] = s[i+1][j+1] = s[i+2][j+1] = s[i+3][j+1] = '.';
        }
    };
    auto check4 = [&](int i , int j){
        if(chk(i,j) && chk(i,j+1) && chk(i+3,j+2) && chk(i+1,j+1) && chk(i+2,j+1) && chk(i+3,j+1)){
            ans++;
            // cout << "done  4" << endl;
            s[i][j] = s[i][j+1] = s[i+3][j+2] = s[i+1][j+1] = s[i+2][j+1] = s[i+3][j+1] = '.';
        }
    };
    auto check5 = [&](int i , int j){
        if(chk(i+1,j)&&chk(i+1,j+1)&&chk(i+1,j+2)&&chk(i+1,j+3)&&chk(i,j+1)&&chk(i+2,j+2)){
            ans++;
            // cout << "done  5" << endl;
            s[i+1][j]=s[i+1][j+1]=s[i+1][j+2]=s[i+1][j+3]=s[i][j+1]=s[i+2][j+2] = '.';
        }
    };
    auto check6 = [&](int i , int j){
        if(chk(i,j+1)&&chk(i+1,j+1)&&chk(i+2,j+1)&&chk(i+3,j+1)&&chk(i+1,j)&&chk(i+1,j+2)){
            ans++;
            // cout << "done  6" << endl;
            s[i][j+1]=s[i+1][j+1]=s[i+2][j+1]=s[i+3][j+1]=s[i+1][j]=s[i+1][j+2]='.';
            // s[i+1][j]=s[i+1][j+1]=s[i+1][j+2]=s[i+1][j+3]=s[i][j+1]=s[i+2][j+1] = 1;
        }
    };
    auto check7 = [&](int i , int j){
        if(chk(i,j)&&chk(i+1,j)&&chk(i+1,j+1)&&chk(i+1,j+2)&&chk(i+2,j+1)&&chk(i+3,j+1)){
            ans++;
            // cout << "done  7" << endl;
            s[i][j]=s[i+1][j]=s[i+1][j+1]=s[i+1][j+2]=s[i+2][j+1]=s[i+3][j+1]='.';
        }
    };
    auto check8 = [&](int i , int j){
        if(chk(i,j)&&chk(i+1,j)&&chk(i+1,j+1) &&chk(i+2,j+1)&&chk(i+3,j+1)&&chk(i+3,j+2)){
            ans++;
            // cout << "done  8" << endl;
            s[i][j]=s[i+1][j]=s[i+1][j+1]=s[i+2][j+1]=s[i+3][j+1]=s[i+3][j+2]='.';
        }
    };
    auto check9 = [&](int i , int j){
        if(chk(i,j)&&chk(i+1,j)&&chk(i+1,j+1) &&chk(i+2,j+1)&&chk(i+3,j+1)&&chk(i+2,j+2)){
            ans++;
            // cout << "done  9" << endl;
            s[i][j]=s[i+1][j]=s[i+1][j+1]=s[i+2][j+1]=s[i+3][j+1]=s[i+2][j+2]='.';
        }
    };
    auto check10 = [&](int i , int j){
        if(chk(i,j)&&chk(i+1,j)&&chk(i+1,j+1)&&chk(i+2,j+1)&&chk(i+2,j+2)&&chk(i+3,j+2)){
            ans++;
            // cout << "done  10" << endl;
            s[i][j]=s[i+1][j]=s[i+1][j+1]=s[i+2][j+1]=s[i+2][j+2]=s[i+3][j+2]='.';
        }
    };
    auto check11 = [&](int i , int j){
        if(chk(i,j)&&chk(i,j+1)&&chk(i,j+2)&&chk(i+1,j+2)&&chk(i+1,j+3)&&chk(i+1,j+4)){
            ans++;
            // cout << "done  11" << endl;
            s[i][j]=s[i][j+1]=s[i][j+2]=s[i+1][j+2]=s[i+1][j+3]=s[i+1][j+4] = '.';
        }
    };
    int fl = 1;
    auto clockwise = [&](){
        char tp[25][25];
        /*
        1  1 2 3 ... m
        2
        .
        .
        n
        */
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                tp[i][j] = s[n+1-j][i]; 
            }
        }
        swap(n , m);
        for(int i = 1; i <=n; i++){
            for(int j = 1; j <= m; j++){
                s[i][j] = tp[i][j];
            }
        }
        if(!fl){
        cout << "clockwise" << endl;
        cout << " -- begin -- " << endl;
        cout << "n === " << n << " m == " << m << endl;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                s[i][j] = tp[i][j];
                cout << s[i][j];
            }cout << endl;
        }
        // cout << "-- end -- " << endl;
        // fl=0;
        }
    };
    auto mirror = [&](){
        char tp[25][25];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                tp[i][j] = s[i][m+1-j];
            }
        }
        //cout << " mirror   show  " << endl;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                s[i][j] = tp[i][j];
           //     cout << s[i][j];
            }
         //   cout << endl;
        }
    };
    // cout << " now ==== " << endl; 
    // check6(1,2);
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= m; j++){
    //         cout << s[i][j];
    //     }
    //     cout << endl;
    // }
    auto up = [&](){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                check1(i , j);
                check2(i , j);
                check3(i , j);
                check4(i , j);
                check5(i , j);
                check6(i , j);
                check7(i , j);
                check8(i , j);
                check9(i , j);
                check10(i , j);
                check11(i , j);
            }
        }
    };
    auto show = [&](){
        // for(int i = 1; i <= n; i++){
        //     for(int j = 1; j <= m; j++){
        //         cout << s[i][j];
        //     }cout << endl;
        // }
    };
    up();show();
    clockwise(); up();show();
    clockwise(); up();show();
    clockwise(); up();show();
    clockwise(); show();
    mirror();show();
    up();show();
    clockwise(); up();show();
    clockwise(); up();show();
    clockwise(); up();show();
    cout << ans << endl;
    return 0;
}

FB:

code by 广州全能王

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;

const int N = 25;

int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int tf[4][6]={
	{1,2,3,0,4,5},
	{3,0,1,2,4,5},
	{5,1,4,3,0,2},
	{4,1,5,3,2,0}
};

int v[6];

char a[N][N];

	int n,m;
int ok(int x,int y){
	return x>=0 && x<n && y>=0 && y<m && a[x][y]=='O';
}

void g(int x){
	int tmp[6];
	for(int i=0;i<6;i++) tmp[i]=v[i];
	for(int i=0;i<6;i++) v[tf[x][i]]=tmp[i];
}

int f(int x,int y){
	a[x][y]='.';
	int re=v[0]?-10000:1;
	v[0]=1;
	for(int i=0;i<4;i++){
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(ok(tx,ty)){
			g(i);
			re+=f(tx,ty);
			g(i^1);
		}
	}
	return re;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%s",a+i);
	int ans=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(a[i][j]=='O') {
				memset(v,0,24);
				ans+=(f(i,j)==6);
			}
	printf("%d\n",ans);
}

J:PaperCubexpress

Description

$n$ 次查询,每组查询有两个字符串$a, b$。$a$ 表示学校的名字，$b$ 表示邮寄的物品编号组成的字符串。判断bb字符串是否是 $10$ 个 $O$，3个 $W$ ，$1$ 个$N$，$1$个 $B$，一个$K$组成的.

Code

First Blood by team76093

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
char ch[100010];
int a[1001];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(a,0,sizeof(a));
		scanf("%s%s",ch,ch);
		int l=strlen(ch);
		for(int i=0;i<l;i++)
		{
			if(ch[i]=='O')a[1]++;
			else if(ch[i]=='W')a[2]++;
			else if(ch[i]=='K')a[3]++;
			else if(ch[i]=='B')a[4]++;
			else if(ch[i]=='N')a[5]++;
			else a[6]++;
		}
		if(a[1]==10&&a[2]==3&&a[3]==1&&a[4]==1&&a[5]==1&&a[6]==0)
		puts("YES");
		else puts("NO");
	}
}

K:PaperCase

Description

多组输入到文件尾，给一些用空格隔开的单词，用驼峰命名法来表示它们。骆驼式命名法就是当变量名或函数名是由一个或多个单词连结在一起时，第一个单词以小写字母开始；从第二个单词开始以后的每个单词的首字母都采用大写字母。

Code

First Blood by team76009

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int N = 1e6+10;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string s;
	while(getline(cin,s)){
		int n = s.length();
		for(int i=0; i<n; i++){
			if(s[i]==' ')cout<<(char)(s[i+1]-'a'+'A'),i++;
			else cout<<s[i]; 
		}
		cout<<endl;
	}	 
	return 0;
}

-------------本文结束感谢您的阅读-------------